// 执行消耗内存为 11776 kb 的范例
#include <stdio.h>

void swap(int *a, int i, int j, int *numsIndex) {
	if (i == j)
		return;
	int tmp = a[i] + a[j];
	a[i] = tmp - a[i];
	a[j] = tmp - a[j];
	tmp = numsIndex[i] + numsIndex[j];
	numsIndex[i] = tmp - numsIndex[i];
	numsIndex[j] = tmp - numsIndex[j];
}

int getMedium(int a1, int a2, int a3, int *a) {
	if ((a[a1] >= a[a2] && a[a2] >= a[a3])
			|| (a[a3] >= a[a2] && a[a2] >= a[a1]))
		return a2;
	else if ((a[a2] >= a[a1] && a[a1] >= a[a3])
			|| (a[a3] >= a[a1] && a[a1] >= a[a2]))
		return a1;
	return a3;
}

void my_qsort(int *a, int i, int j, int * numsIndex) {
	if (i >= j)
		return;
	if (j - i == 1) {
		if (a[i] > a[j])
			swap(a, i, j, numsIndex);
		return;
	}

	int p = i, tmp_i = i;
	int q = j + 1, tmp_j = j;
	int tmp_base = (i + j) / 2;
	int base_index = getMedium(tmp_i, tmp_j, tmp_base, a);
	int base = a[base_index];

	swap(a, tmp_i, base_index, numsIndex); //比较基数放到序列前端

	while (i != j) {
		if (a[j] >= base) {
			if (a[j] == base) {
				swap(a, j, q - 1, numsIndex);
				q--;
			}
			j--;
		} else if (a[i] <= base) {
			if (a[i] == base && i != p) {
				swap(a, i, p + 1, numsIndex);
				p++;
			}
			i++;
		} else {
			swap(a, i, j, numsIndex);
			j--;
		}
	}
//	swap(a, i, tmp_i, numsIndex); // Swap base and logic medium element
	int left_equal_len = p-tmp_i + 1;
	int right_equal_len =  (tmp_j - q)>=0?(tmp_j - q) + 1 : 0;

	for (int _i = 0; _i < left_equal_len ; _i++)
		swap(a, tmp_i + _i, i - _i, numsIndex); //左侧与base相等的值放到ij相遇的左边

	for (int _i = 0; _i < right_equal_len; _i++)
		swap(a, tmp_j - _i , i + 1 + _i, numsIndex); //右侧与base相等的值放到ij相遇的右边

	my_qsort(a, tmp_i, i - left_equal_len, numsIndex);
	my_qsort(a, j + 1 + right_equal_len, tmp_j, numsIndex);
	return;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
	int *returnList = (int *) malloc(2 * sizeof(int));
	int numsIndex[numsSize];
	for (int i = 0; i < numsSize; i++) numsIndex[i] = i;

	my_qsort(nums, 0, numsSize - 1, numsIndex);
//	for (int i = 0; i < numsSize; i++) {
//		printf("%d,", nums[i]);
//	}
	int i = 0;
	int j = numsSize - 1;
	while (i != j) {
		if (nums[i] + nums[j] > target)
			j--;
		else if (nums[i] + nums[j] < target)
			i++;
		else {
			returnList[0] = numsIndex[i];
			returnList[1] = numsIndex[j];
			*returnSize = 2;
			return returnList;
		}
	}
	*returnSize = 0;
	return returnList;
}